Many computer programs are computationally intensive, meaning that they require large amounts of computing power. As a consequence, these programs may execute more slowly than the computer user desires, even on the fastest computers. One way of increasing the execution speed of a computationally intensive computer program is to divide the program into multiple units, or loci, of concurrent execution. These units of execution are known as xe2x80x9cthreadsxe2x80x9d. A program with multiple threads of execution is known as a xe2x80x9cmultithreaded programxe2x80x9d. A program with only a single thread of execution is known as a xe2x80x9csequential programxe2x80x9d. The threads that make up a multithreaded program may be executed concurrently on multiple computer processors, allowing many operations in the program to be carried out simultaneously, thereby speeding up program execution.
In a multithreaded program, the program or operating system must control the access of threads to data objects in the program, in order to the prevent the multiple threads from concurrently accessing the same data object in an undesirable manner. If multiple threads modify the same data object concurrently, or read and modify the same data object concurrently, the resulting state of the program is extremely difficult to determine. Developing a multithreaded program is significantly more difficult than developing a sequential program because of the problems of (1) expressing the division of a program into multiple threads and (2) structuring and controlling the access of those threads to data objects.
The present application teaches a structured thread (xe2x80x9cSthreadxe2x80x9d) system with thread synchronization and production mechanisms.
Another aspect produces multithreadable code. The multithreadable code can be annotated using information indicative of its multithreadability. The multithreadable code constructs are code constructs that can be executed in a multithreadable manner, or equivalently in a sequential manner. Multithreadable code constructs may be expressed by annotating sequential code constructs to indicate that their multithreaded execution is equivalent to sequential execution. The multithreadable code can be used along with multithreaded code. Specific instances of a multithreadable constructs: a multithreadable block, and a multithreadable for loop, and are disclosed.
The second aspect of the system is the integration of multithreadable code constructs with traditional explicitly multithreaded code constructs. Explicitly multithreaded code constructs must always be executed in a multithreaded manner. Examples of explicitly multithreaded code constructs include multithreaded block constructs, multithreaded for loop constructs, and library-based thread creation functions. Multithreadable code constructs and explicitly multithreaded code constructs may be intermingled within a program as required, with well-defined meaning.
According to a first aspect, a special counter called an xe2x80x9cs-counterxe2x80x9d, is used as a thread synchronization mechanism.
Special xe2x80x9cs-Flagsxe2x80x9d can also be used for thread synchronization, and flag synchronization is also described herein.
Yet another aspect is the implementation of the programming system within an existing compiler environment using a special pre-processing system.
The embodiments of the invention describe additional details, including the following:
The s-counter synchronizing the access of threads to shared data objects. The mechanisms use xe2x80x9cmonotonicxe2x80x9d synchronization objects, with operations that can be constrained to only move the value of the object in one direction. Monotonic synchronization objects can be used to synchronize the access of threads to shared data objects in multithreadable code constructs in a manner that guarantees the equivalence of sequential and multithreaded execution. Specific instances of monotonic synchronization objects are disclosed, namely a form of counter called an xe2x80x9cs-counterxe2x80x9d and a form of flag called an xe2x80x9cs-flagxe2x80x9d. The s-counter is a particularly powerful thread synchronization mechanism in many contexts, with its use in multithreadable code constructs being one example.
The application describes implementation of the multithreaded programming system within an existing program development and compilation environment using a special source-to-source preprocessing system and high-level thread library. This allows the system to be transparently and seamlessly integrated with existing programming systems such as Microsoft Visual Studio for the Microsoft Windows family of operating systems, the GNU program development tools for Linux and other versions of the Unix operating system, or on any version of the Java programming language, for example.